#!/usr/bin/python
# -*- coding:utf-8 -*-
#�鲢����
#@author: wklken@yeah.net



def merge(l1,l2):
    result = []
    while l1 and l2:
        result.append( l1.pop(0) if l1[0]< l2[0] else l2.pop(0))
    return result + l1  + l2

#递归版本
def merge_sort(l):
    if len(l) <= 1:
        return l
    mid = len(l)/2
    return merge(merge_sort(l[:mid]), merge_sort(l[mid:]))

#非递归版本，待实现
def merge_sort_2(l):
    """mergesort的非递归版本，from DPV's <<Algorithms>>   改进了下
       http://www.cs.berkeley.edu/~vazirani/algorithms.html
    """
    Q = [ [i] for i in l ]
    while(len(Q)>1):
        Q.append(merge(Q.pop(0), Q.pop(0)))
        
    return Q.pop()
    

l = [8, 4, 3, 7, 6, 5, 2, 1]
print merge_sort(l)
print merge_sort_2(l)